1. Field of the Invention
The present invention relates to a divider and more particularly to a higher-radix type of digital divider.
The present application claims priority of Japanese Patent Application No.2000-029524 filed on Feb. 7, 2000, which is hereby incorporated by reference.
2. Description of the Related Art
For example, in “Design of a Radix-4 Divider Without a Quotient Selection Table” by O. Miura, et al. (Proceedings of the 1998 Conference of The Institute of Electronics, Information and Communication Engineers, Japan, Electronics [2]), a higher-radix divider to be implemented on an LSI (Large Scale Integrated circuit) is introduced.
As a divider that can be implemented on the LSI, the divider using a subtraction shift method or a subtraction non-restoring method as a division algorithm is generally used because a divider using such division algorithms can provide well-balanced amounts of hardware and performance. Such division algorithms can be performed in a same way as division is done normally using figures on a piece of paper, that is, it is a method in which the division is done by obtaining a quotient, shifting a remainder (that is, a partial remainder) and subtracting a multiple of a denominator (a divisor) from the quotient. A variety of the division algorithms including restoring division, non-restoring division, SRT (Sweeney, Robertson and Tocher) division, generalized SRT division methods are disclosed in “High-speed Operation Methods of a Computer” (Kindai Kagaku Co., Ltd. 1980).
First, a general-purpose procedure for division using the subtraction shift method is briefly explained below. Let it be presumed that a bit length for an operation is n (an arbitrary positive integer), a radix for the operation is r, a divisor is D, a dividend is R (0), a partial remainder obtained by j-th time operations is R (j) (j is an integer being zero or greater) and a quotient obtained by the j-th time operation is q (j) (j is the integer being zero or greater). Also, let it be assumed that the divisor D and the dividend R (0) have been normalized. Moreover, let it be assumed that, as a normalized floating-point format, ┌1. xxxx┘ is used. Even when data form not matching with the normalized floating-point format is dealt, by performing an appropriate shift processing before and after operations, the data format can be treated in the normalized floating-point format.
The quotient and partial remainder used in this method are represented by a redundant binary notation. That is, if twos complement notation is employed, each bit is represented as {0, 1}, however, in this method, ternary {−1, 0, 1} can be taken and a negative number can be also used.
Under such conditions as input data is normalized as described above, the quotient and partial remainder can be sequentially obtained by using the following recurrence equation (1):
 R(j+1)=r×R(j)−q(j+1)×D  (1).
At this point, the quotient q (j+1) is selected from digit set defined by the radix r in a manner so as to satisfy the following equation (2):0≦|R(j+1) |<k×D  (2)where k represents a constant that satisfies the following equation (3):k=m/(r−1)  (3)where m represents a digit having a largest absolute value out of the digit set in a mathematical system of the radix r. In this case, since a minimum value of m is ½×r and a maximum value is r−1, a range of the k is given by the following expression (4):½≦k<1  (4).When the mathematical system of the radix 4 is taken as an example, the digit set possibly includes two states: {−3, −2, −1, 0, 1, 2, 3} and {−2, −1, 0, 1, 2}. In the former case, k=1 and, in the latter case, k=⅔. The equation (2) indicates that the smaller a value of k, the narrower a value range of the partial remainder during operations. That is, since, in the latter case, a tripled number cannot be selected as a multiple of the divisor, by imposing a limitation on the value range of the partial remainder obtained during operations, division is allowed to be done until the multiple of the divisor becomes a double value of the devisor. Moreover, in the case of the mathematical system of the radix of 2, the digit set is {−1, 0, 1} in which k=1. When the quotient is obtained by using the equation (1), since the number of bits of the quotient that can be obtained by one time division is log2r, a quotient having desired number of bits can be obtained by repeating the division by n/log2r times.
The division algorithm described above can be expressed by a graph called a P-D (Partial Remainder-Divisor) plot. FIG. 6 is a graph showing the P-D plot expressing the division algorithm described above. The divisor is plotted as abscissa and the partial remainder obtained by multiplying the divisor by the radix (hereinafter the partial remainder obtained by multiplying the divisor by the radix being referred to simply as a partial remainder obtained after being shifted) as ordinate. However, since the P-D plot is produced so as to be symmetric with respect to an x-axis, only a positive range of a y-axis is shown in the P-D plot. When the division algorithm represented by the P-D plot the quotient can be obtained by making a reference to high-order 2 bits excluding a MSB (Most Significant Bit) of the divisor D and to high-order 5 bits of the partial remainder obtained after being shifted. Let it be assumed that the bits of the partial remainder obtained after being shifted to be referred are represented in twos complement notation. The reference to the MSB of the divisor, since the MSB is assured to be 1 due to normalization, is not required. Since the number of bits of the divisor to be referred is two, an entire P-D plot can be partitioned into four regions depending on the range of the divisor and, in each of the regions, one quotient value can be associated with a value making up of high-order 5 bits represented in a notation of a complement of the partial remainder obtained after being shifted. A pair of high-order 2 bits of the divisor (except its MSB) and high-order 5 bits, in twos complement notation, of the partial remainder obtained after being shifted are representative of values in a specified range on the P-D plot. If high-order 2 bits of the divisor (except its MSB) is Dt, a true divisor D exists in the following range:1+Dt≦D<1+Dt+¼  (5).Moreover, if high-order 5 bits, in twos complement notation, of the partial remainder obtained after being shifted is Rt (j), a true value rR (j) of the partial remainder obtained after being shifted exists in the following range:Rt(j)−½<rR(j)<Rt(j)+½  (6).Since the partial remainder is represented by the redundant binary notation, there is a likelihood that another true value exists in a region in a negative direction with respect to the Rt (j). A rectangular region on the P-D plot expressed by the expressions (5) and (6) is a region where the true divisor and partial remainder exist, which is hereinafter called an uncertain region. To obtain the quotient by making a reference only to high-order bits of the divisor and of the partial remainder means that the quotient is obtained so as to satisfy the equation (2) for all values in the uncertain regions. For example, when 3 is selected as the quotient, a region between a straight line expressed by rR (j)=4D and a straight line expressed by rR (j) =2D, by the equations (1) and (2), is the one where 3 can be selected and only when the uncertain region falls within this range, 3 can be selected. To make the uncertain region larger means that the number of bits of the divisor and partial remainder to be referred is decreased, thus allowing a logic to obtain the quotient to be simplified. Therefore, it is important that a maximum uncertain region is selected while the equations (1) and (2) are satisfied. Moreover, the bits, to be referred, of the partial remainder obtained after being shifted required for obtaining the quotient has to be converted, prior to obtaining the quotient, from the redundant binary notation to the twos complement notation.
In the division algorithm described above, it is necessary to determine the uncertain region by making a reference to two bits existing subsequent to an MSB of the divisor D and high-order 5 bits of the partial remainder obtained after being shifted. At this point, by selecting a multiplication factor so that the divisor falls in any one of the four regions on the P-D plot decided by the referred 2 bits of the divisor and by multiplying, before operations, the divisor and dividend by the multiplication factor, the reference to the 2 bits of the divisor is not required when the quotient is obtained. It is obvious from characteristics of the division that, even if the divisor and the partial remainder are multiplied by a same multiplication factor before operations, no change occurs in the obtained quotient.
Thus, the method in which division is made high-speed by multiplying a coefficient (hereinafter referred to as the multiplication factor) properly selected before start of division is called a scaling. For example, by performing the scaling of the divisor so that a range of the divisor satisfies an expression of 1.50≦the divisor<1.75 and by making non-redundant the high-order 5 bits of the partial remainder obtained after being shifted, that is, by representing the high-order 5 bits in twos complement notation, the quotient can be obtained by referring only to high-order 4 bits of the partial remainder obtained after being shifted. In the scaling method, the multiplication factor is predetermined for every range of the divisor and the divisor is multiplied by the multiplication factor to perform the scaling of the divisor so that the range of the divisor satisfies the expression of 1.50≦the divisor<1.75.
Combination ofRange of divisorMultiplication factormultiple1.125 ≦ divisor < 1.2501.5001 + ½1.125 ≦ divisor < 1.2501.3751 + {fraction (1/4 )} + ⅛1.250 ≦ divisor < 1.3751.2501 + ¼1.375 ≦ divisor < 1.5001.1251 + ⅛1.500 ≦ divisor < 1.6251.00011.625 ≦ divisor < 1.7501.00011.750 ≦ divisor < 1.8750.8751 − ⅛1.875 ≦ divisor < 2.0000.8751 − ⅛
Moreover, the above multiplication factor, since it can be implemented by combination of a multiple of ±½n (however, the n is a natural number including 0) as shown in the above combination of multiples, can be produced by only shifting and addition. To identify the range of the above divisor, reference to high-order 3 bits of the divisor except its MSB is all that is needed. The reference to the MSB of the divisor, since the MSB is assured to be always 1 due to normalization, is not required. As a result of the above multiplication, the scaling of the divisor is performed so that a range of the divisor satisfies an expression of 1.50≦divisor<1.75. FIG. 7 is a graph showing another P-D plot expressing the division algorithm. In the division algorithm shown in FIG. 7, the reference to the divisor is not required and, moreover, expansion of the uncertain region by 1.5-fold in a y-direction is made possible, unlike the case where no scaling of the uncertain region is performed, thus allowing bits of the partial remainder obtained after being shifted to be referred to be only high-order 4 bits represented in the twos complement notation.
Next, the conventional technology will be explained by referring to FIGS. 4 and 5. FIG. 4 is a schematic block diagram showing one example of configurations of a conventional divider. It is assumed in the example that the radix for operations is 4, the digit set is {−3, −2, −1, 0, 1, 2, 3}, both the divisor and dividend are decimals with a bit length of n and the generalized SRT division algorithm is used for operations. Moreover, the divisor and the dividend are input by 53 bits.
As shown in FIG. 4, the conventional divider is provided with a scaling factor generating section 11, a 53 bits×4 bits multiplier 21, a 53 bits×4 bits multiplier 31, a divisor tripled-number generating section 41, a repetitive operating section 51, a quotient register 61 and an adder 71. The scaling factor generating section 11 is adapted to generate the multiplication factor used for a scaling process. The 53 bits×4 bits multiplier 21 is adapted to multiply an input 53-bit divisor by an output from the scaling factor generating section 11 and outputs a result. The 53 bits×4 bits multiplier 31 is adapted to multiply an input 53-bit dividend by an output from the scaling factor generating section 11 and outputs a result. The divisor tripled-number generating section 41 is adapted to triple the output from the 53 bits×4 bits multiplier 21 and outputs a result. The repetitive operating section 51 is adapted to calculate a quotient by performing repetitive operations of the divisor (56 bits) being an output of the 53 bits×4 bits multiplier 21, a tripled number of the divisor (57 bits) being an output from the divisor tripled-number generating section 41 and a dividend (56 bits) being an output from the 53 bits×4 bits multiplier 31. The quotient register 61 is adapted to store an output from the repetitive operating section 51. The adder 71 is adapted to represent the quotient in the twos complement notation. FIG. 5 is a schematic circuit diagram showing one of examples of detailed configurations of the repetitive operating section 51 employed in the conventional divider of FIG. 4.
Next, operations of the divider shown in FIG. 4 will be described below. High-order 3 bits ([2:4]) except an MSB of the divisor are input to the scaling factor generating section 11 and the generated multiplication factor is input to the 53 bits×4 bits multiplier 21 and the 53 bits×4 bits multiplier 31. The multiplication factor to be here input is a value represented by 4 bits. In the 53 bits×4 bits multiplier 21 and the 53 bits×4 bits multiplier 31, the divisor and dividend are multiplied by the multiplication factor and the resulting divisor and dividend are output as values represented by 56 bits. The divisor tripled-number generating section 41 generates a 57-bit tripled number of the divisor by using the 56-bit divisor.
Next, each of the divisor represented by 56 bits, tripled number of the divisor represented by 57 bits and the dividend represented by 56 bits is input to the repetitive operating section 51. Then, in the repetitive operating section 51, division processing using the input three values is performed repeatedly to obtain a quotient.
The quotients generated by the repetitive operating section 51 are registered in the quotient register 61 and, finally, after enough quotients to satisfy the required number of bits have become available, the quotients are converted so that they are represented in the twos complement notation to become normal digits which are then output to terminate the division.
However, in the conventional divisor using the scaling technique as shown in FIG. 4, in order to select a quotient by referring to high-order 4 bits (represented in the twos complement notation) of the partial remainder obtained after being shifted, it is necessary to represent high-order 5 bits of the partial remainder obtained after being shifted in the twos complement notation. This causes a delay in computation and decreased flexibility in a circuit area in a twos complement converting circuit embedded in the repetitive operating section 51. In the repetitive operating section 51 in particular, since repetitive division processing is performed, if the repetitive operating section 51 is complicated in circuit configurations, speed of the division processing decreases accordingly.